SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Nondeterministic algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Nondeterministic algorithm</span></span>

</h1>

</header>

<p>In <a href="Computer_science" title="Computer science">computer science</a> and <a href="Computer_programming" title="Computer programming">computer programming</a>, a <b>nondeterministic algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> that, even for the same input, can exhibit different behaviors on different runs, as opposed to a <a href="Deterministic_algorithm" title="Deterministic algorithm">deterministic algorithm</a>.

</p><p>Different <a href="Model_of_computation" title="Model of computation">models of computation</a> give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness:

</p>

<ul><li>A <a href="Concurrent_algorithm" class="mw-redirect" title="Concurrent algorithm">concurrent algorithm</a> can perform differently on different runs due to a <a href="Race_condition" title="Race condition">race condition</a>. This can happen even with a single-threaded algorithm when it interacts with resources external to it. In general, such an algorithm is considered to perform correctly only when <i>all</i> possible runs produce the desired results.</li>

<li>A <a href="Probabilistic_algorithm" class="mw-redirect" title="Probabilistic algorithm">probabilistic algorithm</a>'s behavior depends on a <a href="Random_number_generator" class="mw-redirect" title="Random number generator">random number generator</a> called by the algorithm. These are subdivided into <a href="Las_Vegas_algorithm" title="Las Vegas algorithm">Las Vegas algorithms</a>, for which (like concurrent algorithms) all runs must produce correct output, and <a href="Monte_Carlo_algorithm" title="Monte Carlo algorithm">Monte Carlo algorithms</a> which are allowed to fail or produce incorrect results with low probability. The performance of such an algorithm is often measured probabilistically, for instance using an analysis of its <a href="Expected_time" class="mw-redirect" title="Expected time">expected time</a>.</li>

<li>In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, nondeterminism is often modeled using an explicit mechanism for making a nondeterministic choice, such as in a <a href="Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">nondeterministic Turing machine</a>. For these models, a nondeterministic algorithm is considered to perform correctly when, for each input, <i>there exists</i> a run that produces the desired result, even when other runs produce incorrect results. This existential power makes nondeterministic algorithms of this sort more efficient than known deterministic algorithms for many problems. The <a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a> encapsulates this conjectured greater efficiency available to nondeterministic algorithms. Algorithms of this sort are used to define <a href="Complexity_class" title="Complexity class">complexity classes</a> based on <a href="Nondeterministic_time" class="mw-redirect" title="Nondeterministic time">nondeterministic time</a> and <a href="Nondeterministic_space" class="mw-redirect" title="Nondeterministic space">nondeterministic space</a> complexity. They may be simulated using <a href="Nondeterministic_programming" title="Nondeterministic programming">nondeterministic programming</a>, a method for specifying nondeterministic algorithms and searching for the choices that lead to a correct run, often using a <a href="Backtracking_search" class="mw-redirect" title="Backtracking search">backtracking search</a>.</li></ul>

<p>The notion of nondeterminism was introduced by <a href="Robert_W._Floyd" title="Robert W. Floyd">Robert W. Floyd</a> in 1967.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRobert_W.Floyd1967" class="citation journal cs1">Robert W.Floyd (October 1967). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321420.321422">"Nondeterministic Algorithms"</a>. <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>. <b>14</b> (4): <span class="nowrap">636–</span>644. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321420.321422">10.1145/321420.321422</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1990464">1990464</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFCormen,_Thomas_H.2009" class="citation book cs1">Cormen, Thomas H. (2009). <i>Introduction to Algorithms</i> (3rd ed.). MIT Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03384-8</bdi>.</cite></li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://xlinux.nist.gov/dads/HTML/nondetermAlgo.html">"Nondeterministic algorithm"</a>. National Institute of Standards and Technology<span class="reference-accessdate">. Retrieved <span class="nowrap">July 7,</span> 2013</span>.</cite></li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html">"Non-deterministic Algorithms"</a>. New York University Computer Science<span class="reference-accessdate">. Retrieved <span class="nowrap">July 7,</span> 2013</span>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-07-07" href="https://en.wikipedia.org/wiki/?title=Nondeterministic_algorithm&oldid=1233091157">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>